package 第三次实验.第三个实验;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * Searching demonstrates various search algorithms on an array 
 * of objects.
 *
 * @author Lewis and Chase
 * @version 4.0 
 */
public class Searching 
{
    public static <T> boolean linearSearch(T[] data, int min, int max, T target)
    {
        int index = min;
        boolean found = false;

        while (!found && index <= max) 
        {
            found = data[index].equals(target);
            index++;
        }

        return found;
    }


    public static <T extends Comparable<T>> boolean binarySearch(T[] data, int min, int max, T target)
    {  
        boolean found = false;
        int midpoint = (min + max) / 2;  // determine the midpoint

        if (data[midpoint].compareTo(target) == 0)
            found = true;

        else if (data[midpoint].compareTo(target) > 0)
        {
            if (min <= midpoint - 1)
                found = binarySearch(data, min, midpoint - 1, target);
        }
        
        else if (midpoint + 1 <= max)
            found = binarySearch(data, midpoint + 1, max, target);

        return found;
    }
    public static int InsertionSearch(int a[], int value, int low, int high){
        int result=0;
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value) {
           result= a[mid];
        }
        if(a[mid]>value) {
            return InsertionSearch(a, value, low, mid-1);
        }
        if(a[mid]<value) {
            return InsertionSearch(a, value, mid+1, high);
        }
        return result;
    }

public static boolean InsertionSearch(int a[], int value){
       if (InsertionSearch(a,value,0,a.length-1)==value){
           return true;
       }
       else {
           return false;
       }

}


    public static boolean fibonacciSearch(int[] table, int keyWord) {

        int i = 0;
        while (getFibonacci(i) - 1 == table.length) {
            i++;
        }

        int low = 0;
        int height = table.length - 1;
        while (low <= height) {
            int mid = low + getFibonacci(i - 1);
            if (table[mid] == keyWord) {
                return true;
            } else if (table[mid] > keyWord) {
                height = mid - 1;
                i--;
            } else if (table[mid] < keyWord) {
                low = mid + 1;
                i =i- 2;
            }
        }
        return false;
    }


    public static int getFibonacci(int n) {
        int res = 0;
        if (n == 0) {
            res = 0;
        } else if (n == 1) {
            res = 1;
        } else {
            int first = 0;
            int second = 1;
            for (int i = 2; i <= n; i++) {
                res = first + second;
                first = second;
                second = res;
            }
        }
        return res;
    }
    public static boolean  SearchTree(int[] a ,int value){
        LinkedBinarySearchTree c =new LinkedBinarySearchTree();
        for (int i =0;i<a.length;i++){
            c.addElement(a[i]);
        }
        return c.find1(value);

    }
    public static void hashinsert(int[] hashTable, int target) {

        int hashAddress = hash(hashTable, target);
        while (hashTable[hashAddress] != 0) {
            hashAddress = (++hashAddress) % hashTable.length;
        }
        hashTable[hashAddress] = target;
    }
    public static int hashsearch(int[] hashTable, int target) {
        int hashAddress = hash(hashTable, target);
        while (hashTable[hashAddress] != target) {
            hashAddress = (++hashAddress) % hashTable.length;
            if (hashTable[hashAddress] == 0 || hashAddress == hash(hashTable, target)) {
                return -1;
            }
        }
        return hashAddress;
    }
    public static int hash(int[] hashTable, int target) {
        return target % hashTable.length;
    }



    public static boolean BlockSearch(int[] a,int target, int[] index) {

        ArrayList[] list;
        if (null != index && index.length != 0) {

            list = new ArrayList[index.length];
            for (int i = 0; i < list.length; i++) {
                list[i] = new ArrayList();
            }
        }
        else{
            throw new Error("index cannot be null or empty");
        }

        for (int i =0;i<a.length;i++){
            int c = binarySearching(index,a[i]);
            list[c].add(a[i]);
        }

        int i= binarySearching(index,target);
        for(int j=0;j<list[i].size();j++)
        {
            if(target==(int)list[i].get(j))
            {
                return true;
            }
        }
        return false;
    }
    private static int binarySearching(int[] index,int value){
        int start = 0,end =index.length;int mid = -1;
        while(start<=end){
            mid=(start+end)/2;
            if(index[mid]>value){
                end = mid -1;
            }else{

                start = mid+1;
            }
        }
        return start;
    }
    public static void main(String[] args) {
        int a[] = {20,13,23,29};
        Integer[] b = {2,0,1,7,2,3,2,9};
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("差值查找：找16");
        System.out.println(InsertionSearch(a,20));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("斐波那契查找:找99");
        System.out.println(fibonacciSearch(a,29));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(b));
        System.out.println("线性查找：找88");
        System.out.println(linearSearch(b,0,b.length,0));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(b));
        System.out.println("二分查找：找88");
        System.out.println(binarySearch(b,0,b.length,9));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("二分查找树：找99");
        System.out.println(SearchTree(a,29));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("二分查找树：找100");
        System.out.println(SearchTree(a,100));
        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("哈希查找：找29");
        System.out.println("散列表：");
        int[] temp=new int[a.length];
        for (int i =0;i<a.length;i++){
            hashinsert(temp,a[i]);
        }
        System.out.println(Arrays.toString(temp));
        System.out.println("在散列表中的位置为："+hashsearch(temp,29));

        System.out.println();
        System.out.println("数组：");
        System.out.println(Arrays.toString(a));
        System.out.println("分块查找：找29");
        System.out.println(BlockSearch(a,29,new int[]{10,20,30}));

    }
}

